import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int div = partition(arr, left, right);
        quickSort(arr, left, div);
        quickSort(arr, div + 1, right);
    }

    private static int partition(int[] arr, int l, int r) {
        int div = arr[l];
        int s = l, f = r;
        while (s < f) {
            while (f > s && arr[f] >= div) {
                f--;
            }
            while (f > s && arr[s] <= div) {
                s++;
            }
            swap(arr, s, f);
        }
        swap(arr, l, s);
        return s;
    }

    private static void swap(int[] arr, int s, int f) {
        int tmp = arr[s];
        arr[s] = arr[f];
        arr[f] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {8, 4894, 8468, 4684, 684, 68468, 4846, 4, 864, 64, 64, 6, 484, 6, 46, 48, 4, 81, 1, 2, 8, 5, 484, 84, 8, 48, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
//}
//class QuickSort {
//    // 假设按照升序对array数组中[left, right)区间中的元素进行排序
//    void quickSort(int[] array, int left, int right) {
//        if (right - left <= 1)
//            return;
//        // 按照基准值对array数组的 [left, right)区间中的元素进行划分
//        int div = partition(array, left, right);
//        // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
//        // 递归排[left, div)
//        quickSort(array, left, div);
//        // 递归排[div+1, right)
//        quickSort(array, div + 1, right);
//    }
//
//    /**
//     * 士兵法
//     */
//    private static int partition(int[] array, int left, int right) {
//        int i = left;
//        int j = right;
//        int pivot = array[left];
//        while (i < j) {
//            while (i < j && array[j] >= pivot) {
//                j--;
//            }
//            while (i < j && array[i] <= pivot) {
//                i++;
//            }
//            swap(array, i, j);
//        }
//        swap(array, i, left);
//        return i;
//    }
//
//    /**
//     * 挖坑法
//     */
//    private static int partition3(int[] array, int left, int right) {
//        int i = left;
//        int j = right;
//        int pivot = array[left];
//        while (i < j) {
//            while (i < j && array[j] >= pivot) {
//                j--;
//            }
//            array[i] = array[j];
//            while (i < j && array[i] <= pivot) {
//                i++;
//            }
//            array[j] = array[i];
//        }
//        array[i] = pivot;
//        return i;
//    }
//
//
//    public static void swap(int[] arr, int left, int right) {
//        int temp = arr[left];
//        arr[left] = arr[right];
//        arr[right] = temp;
//    }
//
//    public static void main(String[] args) {
//        int[] arr = {8, 5, 8, 752, 4, 5, 8, 874, 55, 5, 874, 5, 5, 9, 952, 48, 6, 2, 5, 6, 32, 5, 6, 8};
//        QuickSort q=new QuickSort();
//        q.quickSort(arr,0, arr.length-1);
//        for (int x :
//                arr) {
//            System.out.println(x);
//        }
//    }
//}
